package com.mdnote.practice.array;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/7 0007
 * @description
 */
public class BinarySearchTemplate {

    public static void main(String[] args) {
        BinarySearchTemplate main = new BinarySearchTemplate();
        int count = main.findMinLengthSum2(new int[]{1, 2, 0, 0}, 2);
        System.out.println(count);
    }

    private int findMinLengthSum(int[] arr, int target) {

        int[] sum = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            sum[i + 1] = sum[i] + arr[i];
        }

        int ans = sum.length;
        for (int i = 0; i < sum.length; i++) {
            int tempAns = search(i + 1, sum.length - 1, sum[i] + target, sum);
            if (tempAns > 0) {
//                ans = Math.min(ans, tempAns);
                return tempAns;
            }
        }
//        return ans == sum.length ? 0 : ans;
        return 0;
    }

    private int search(int start, int end, int target, int[] arr) {

        int left = start, right = end;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= target) {
                if (left == right) {
                    return start - left + 1;
                } else {
                    right = mid;
                }
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
    private int findMinLengthSum2(int[] arr, int target) {
        int ans = arr.length;

        int sum = 0, left = 0, right = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            while (sum >= target && left <= right) {
                ans = Math.min(ans, right - left + 1);
                sum -= arr[left];
                left++;
            }
            right++;
        }

        if (ans == arr.length) {
            return -1;
        }
        return ans;
    }
}
